package fib;

import java.util.HashMap;

public class Solution {
    private int[] arr=new int[31];
    public int fib(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if(n==2){
            return 1;
        }
        if(arr[n]!=0){
            return arr[n];
        }
        int v=fib(n-1)+fib(n-2);
        arr[n]=v;
        return v;
    }
}
//class Solution {
//    public int fib(int n) {
//        double sqrt5 = Math.sqrt(5);
//        double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
//        return (int) Math.round(fibN / sqrt5);
//    }
//} 斐波拉契数列的特征方程 ：x^2=x+1  
